package DP;

import java.util.Scanner;

/**
 * 纯01背包 （给定背包容量 装满背包 的最大价值是多少）
 */

//一刷
public class bag01 {
    /**
     * 二维dp
     * @param w         重量矩阵
     * @param v         价值矩阵
     * @param n         物品
     * @param bagweight 背包容量
     * @return
     */
    public int bag2(int[] w, int[] v, int n, int bagweight) {
        int dp[][] = new int[n][bagweight + 1];

        for (int j = w[0]; j <= bagweight; j++) {
            dp[0][j] = v[0];
        }
        /**
         * dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
         */
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= bagweight; j++) {
                if (j < w[i]) {
                    dp[i][j] = dp[i - 1][j];
                }
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
            }
        }
        return dp[n - 1][bagweight];
    }

    /**
     * 一维dp
     */
    public int bag1(int[] w, int[] v, int n, int bagweight) {
        int[] dp = new int[bagweight + 1];
        /**
         * dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
         */
        for (int i = 0; i < n; i++) {   //遍历物品
            for (int j = bagweight; j >= w[i]; j--) {   //逆序遍历背包
                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        return dp[bagweight];
    }
}


//二刷

/**
 *  二维01背包
 */
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(); // 物品数量
        int n = sc.nextInt(); // 背包容量

        int[] weight = new int[m];
        int[] value = new int[m];

        // 读取重量
        for (int i = 0; i < m; i++) {
            weight[i] = sc.nextInt();
        }

        // 读取价值
        for (int i = 0; i < m; i++) {
            value[i] = sc.nextInt();
        }

        // 动态规划数组，，dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少
        int[][] dp = new int[m][n + 1];

        // 初始化第一行
        for (int j = 0; j <= n; j++) {
            if (j >= weight[0]) {
                dp[0][j] = value[0];
            }
        }

        // 填充dp数组
        for (int i = 1; i < m; i++) {
            for (int j = 0; j <= n; j++) {
                // 不放入当前物品
                dp[i][j] = dp[i - 1][j];

                // 如果可以放入当前物品，比较两种方案
                if (j >= weight[i]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weight[i]] + value[i]);
                }
            }
        }

        // 输出最大价值
        System.out.println(dp[m - 1][n]);

        sc.close(); // 关闭Scanner
    }
}

/**
 * 一维01背包
 */
class main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int weight[] = new int[m];
        int value[] = new int[m];
        for (int i = 0; i < m; i++) {
            weight[i] = sc.nextInt();
        }
        for (int i = 0; i < m; i++) {
            value[i] = sc.nextInt();
        }

        int dp[] = new int[n + 1];

        for (int i = 0; i < m; i++) {//背包
            for (int j = n; j >= weight[i]; j--) {//逆序遍历物品
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        System.out.println(dp[n]);
    }
}